package com.future;

import com.future.util.TreeNode;

/**
 * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 * <p>
 * 有效 二叉搜索树定义如下：
 * <p>
 * 节点的左子树只包含 小于 当前节点的数。
 * 节点的右子树只包含 大于 当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/validate-binary-search-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution_98 {

    public static void main(String[] args) {
        TreeNode L = new TreeNode(10, new TreeNode(5, new TreeNode(4), new TreeNode(8)), new TreeNode(20));
        System.out.println(isValidBST(L));

    }

    /**
     * @param root
     * @return
     */
    public static boolean isValidBST(TreeNode root) {
        return process(root).isBTS;
    }

    public static Info process(TreeNode treeNode) {
        if (treeNode == null) {
            return null;
        }
        Info leftInfo = process(treeNode.left);
        Info rightInfo = process(treeNode.right);
        int max = treeNode.val;
        int min = treeNode.val;
        if (leftInfo != null) {
            max = Math.max(leftInfo.max, max);
            min = Math.min(leftInfo.min, min);
        }
        if (rightInfo != null) {
            max = Math.max(rightInfo.max, max);
            min = Math.min(rightInfo.min, min);
        }
        boolean isBTS = true;
        if (leftInfo != null && !leftInfo.isBTS) {
            isBTS = false;
        }
        if (rightInfo != null && !rightInfo.isBTS) {
            isBTS = false;
        }
        boolean leftMaxLessCurr = leftInfo == null ? true : (leftInfo.max < treeNode.val);
        boolean rightMaxMoreCurr = rightInfo == null ? true : (rightInfo.min > treeNode.val);
        if (!leftMaxLessCurr || !rightMaxMoreCurr) {
            isBTS = false;
        }
        return new Info(isBTS, max, min);
    }

    public static class Info {
        public boolean isBTS;
        public int max;
        public int min;

        public Info(boolean isBTS, int max, int min) {
            this.isBTS = isBTS;
            this.max = max;
            this.min = min;
        }
    }

}
